The present invention pertains to the field of computer graphics. In particular, the present invention pertains to a method for clipping three-dimensional computer graphics images that are rendered using tetrahedrons.
There are many applications, such as computed tomography and magnetic resonance in the medical field, in which data exist in three-dimensional scalar fields. Using three-dimensional computer graphics techniques, the data are used to define an image that can be displayed in a suitable visual form in order to facilitate the analysis, interpretation, and exchange of information.
The image is framed using geometric shapes composed of lines and polygons. The derivation of the vertices of the geometric shapes and the manipulation of these vertices to provide the image entail numerous geometric calculations so that the image portrayed on the display screen has the appearance and characteristics of a three-dimensional object. For example, the displayed object can be rotated so that it can be viewed as if from different directions. The object can also be cut or sliced (xe2x80x9cclippedxe2x80x9d) so that its internal features can be viewed, or so that aspects of the object can be magnified or highlighted for enhanced imaging.
With reference to Prior Art FIG. 1A, prior art techniques for displaying data in three-dimensions typically use cubes or tetrahedrons to render the object. For example, eight adjacent pixels in an image can be connected to form a cube (four pixels in each of two adjacent planes). The cube can then be divided into a collection of five tetrahedrons. Prior Art FIG. 1A is a volumetric representation of a cube 110 using five tetrahedrons. The use of tetrahedrons to represent objects in computer graphics is exemplified by the Volumizer program by Silicon Graphics, Inc. (SGI), of Mountain View, Calif.
Prior Art FIG. 1B illustrates a more complex object 120 rendered using tetrahedrons. In one prior art technique, object 120 is clipped using a graphics design program (such as OpenGL, also by SGI) executed by a graphics computer system. The user specifies what portion of object 120 is to be clipped using a known mechanism (e.g., the computer system""s mouse is used to indicate where a cut is to be made). In the prior art, the graphics design program operates one by one on each of the five tetrahedrons describing object 120. The computer system then displays the resulting image.
The calculations required for clipping an object are numerous and complex. For example, consider an object rendered using a number of tetrahedrons. When a cut is made through the object, portions of each tetrahedron will have to be removed. One or more vertices will remain from the original object and one or more new vertices will be formed. In order to render the remaining object using tetrahedrons, it is necessary to compute how to connect the remaining vertices with the new vertices in order to form new tetrahedrons that render the remaining object. That is, after the clipping occurs, it is necessary to calculate how to arrange tetrahedrons in and around the remaining volume so that the remaining volume is accurately depicted. The computations needed to complete these calculations are mathematically complex and time consuming. The difficulties associated with these computations also limit the complexity of the clipped objects that can be rendered.
Typically, the preference is to perform these graphics calculations rapidly so that the resultant image is displayed as quickly as possible. Consequently, in the prior art, hardware solutions (such as processors and computer systems) are designed specifically to execute graphics programs rapidly in order to accelerate graphics calculations.
Unfortunately, these prior art hardware solutions are not capable of providing analytical information pertaining to the clipping operation. For example, the coordinates of the points where cuts are made cannot be provided, nor are the coordinates stored in memory so that they can be subsequently retrieved. However, in some cases it is desirable that the analytical information pertaining to the clipping operation be available or retrievable. For instance, that information could be stored in a database for subsequent retrieval and use.
Another problem with the prior art techniques is that, after the clipping operation is performed, only the portion of the object that remains is available to be displayed to the user. The portion of the object that was removed cannot be retrieved and displayed.
In Carneiro et al., xe2x80x9cTetra-Cubes: An algorithm to generate 3D iso-surfaces based upon tetrahedraxe2x80x9d (SIBGRAPI, October 1996), a technique is described for generating iso-surfaces from data represented using tetrahedrons. However, that technique is for generating surfaces represented as triangles. The technique described by Carneiro et al. is not applicable to the more complex problem of rendering three-dimensional volumes using tetrahedrons. In particular, Carneiro et al. is not applicable to the more complex case where new tetrahedrons need to be computed in order to render an object that has been clipped from another object.
Accordingly, what is needed is a mechanism for clipping virtual objects that provides to the user or stores in a database the analytical information resulting from the clipping operation. What is further needed is a mechanism that accomplishes the above and also functions quickly and efficiently to calculate geometric shapes (e.g., tetrahedrons) for accurately rendering a clipped object as well as the portion of the object that is removed. The present invention provides a novel solution to the above needs.
These and other objects and advantages of the present invention will become obvious to those of ordinary skill in the art after having read the following detailed description of the preferred embodiments which are illustrated in the various drawing figures.
The present invention provides a mechanism for clipping virtual objects that makes available to the user or stores in a database the analytical information resulting from the clipping operation. The present invention also functions quickly and efficiently to calculate geometric shapes (e.g., tetrahedrons) for accurately and rendering a clipped object as well as the portion of the object that is removed.
The present invention pertains to a method for generating a three-dimensional computer graphics image. In particular, the present invention pertains to a method for generating an image of a clipped object.
The object is rendered using a plurality of three-dimensional geometric shapes. In the present embodiment, the geometric shapes are tetrahedrons. In the present embodiment, one or more of the tetrahedrons is intersected by a planar surface, thereby dividing the tetrahedron into a first subvolume and a second subvolume. That is, the volume is clipped, and a portion of the object is removed. In this case, the first subvolume contains the portion of the object that is retained and the second subvolume contains the portion of the object that is removed.
A new vertex is created at each intersection of the planar surface with an edge of a tetrahedron. Each vertex of the tetrahedron is categorized as lying on one side of the planar surface or the other. Each vertex lying on the side of the planar surface that is in the first subvolume is placed into a first group.
The first group is used to select a set of instructions. In one embodiment, each vertex of the geometric shape is uniquely identified. Thus, the first group of vertices contains a unique combination of vertex identifiers that allow a particular set of instructions pertaining to that combination to be selected.
In one embodiment, the set of instructions are contained in a lookup table. The vertices in the first group and each new vertex are connected according to the set of instructions to form three-dimensional tetrahedrons rendering the first subvolume (e.g., the portion of the volume that is retained).
In one embodiment of the present invention, the set of instructions also specify which edges of the geometric shape are intersected by the planar surface.
In one embodiment, each vertex of the geometric shape categorized as lying on the other side of the planar surface (e.g., in the second subvolume) is placed into a second group. The second group is used to select a second set of instructions pertaining to the unique combination of vertex identifiers in the second group. The vertices in the second group and each new vertex are connected according to the set of instructions to form three-dimensional geometric shapes rendering the second subvolume (e.g., the portion of the volume that was removed).
The present invention thus provides an analytical approach for clipping an object. Consequently, the results generated in accordance with the present invention can be stored in a database and subsequently retrieved. The set of instructions specifying how vertices are to be connected to render a clipped object are computed beforehand and, in one embodiment, stored in a lookup table. Because the instructions are computed beforehand and readily retrieved from the lookup table, complex and time consuming calculations do not need to be repeatedly performed, and new tetrahedrons are quickly and efficiently calculated. Accordingly, the present invention permits complex objects to be represented after clipping.